package org.example.linkedList;

import org.junit.Test;

import java.util.Arrays;

/**
 * @Auther: wangbw @Date:2020/12/16 @Description: org.example.linkedList @version: 1.0
 */
public class TestSort {
    public static void print(int[] arr) {
        System.out.println("result:" + Arrays.toString(arr));
    }

    @Test
    public void getK() {
        int k = 3;
        int[] arr = new int[]{4, 2, 5, 12, 3};
        if (k > arr.length) System.out.println("no");
        int res = 0;
        int start = 0;
        int end = arr.length - 1;
        while (true) {
            res = part(arr, start, end);
            if (res + 1 == k) break;
            if (res + 1 < k) start = res + 1;
            if (res + 1 > k) end = res - 1;
        }
        System.out.println(arr[res]);
    }

    private int part(int[] arr, int lo, int ll) {
        int pivot = arr[lo];
        int i = lo;
        int j = ll + 1;
        while (true) {
            while (i >= ll || arr[++i] < pivot) break;
            while (j <= lo || arr[--j] > pivot) break;
            if (i >= j) break;
            exchange(arr, i, j);
        }
        exchange(arr, j, lo);
        return i;
    }

    private void exchange(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
